package com.jietuo.class02;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2024/3/1
 * @description: 3，用双向链表实现栈和队列
 */
public class Code03_DoubleEndQueueToStackAndQueue {

    public static class Node<T> {
        T data;
        Node<T> last;
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    public static class DoubleEndQueue<T> {
        public Node<T> head;
        public Node<T> tail;

        public void addFromHead(T data) {
            Node<T> cur = new Node<T>(data);
            if (head != null) {
                cur.next = head;
                head.last = cur;
                head = cur;
            } else {
                head = tail = cur;
            }
        }

        public void addFromBottom(T data) {
            Node<T> cur = new Node<T>(data);
            if (head == null) {
                head = tail = cur;
            } else {
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
        }

        public T popFromHead() {
            if (head == null) {
                return null;
            }
            Node<T> cur = head;
            if (head == tail) {
                head = tail = null;
            } else {
                head = head.next;
                head.last = null;
                cur.next = null;
            }
            return cur.data;
        }

        public T popFromBottom() {
            if (tail == null) {
                return null;
            }
            Node<T> cur = tail;
            if (head == tail) {
                head = tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
                cur.last = null;
            }
            return cur.data;
        }

        public boolean isEmpty() {
            return head == null;
        }
    }

    public static class MyStack<T> {

        private DoubleEndQueue<T> doubleEndQueue;

        public MyStack() {
            doubleEndQueue = new DoubleEndQueue<T>();
        }

        public void push(T data) {
            doubleEndQueue.addFromHead(data);
        }

        public T pop() {
            return doubleEndQueue.popFromHead();
        }
    }

    public static class MyQueue<T>{
        private DoubleEndQueue<T> doubleEndQueue;

        public MyQueue(){
            doubleEndQueue = new DoubleEndQueue<T>();
        }

        public void push(T data) {
            doubleEndQueue.addFromBottom(data);
        }

        public T pop() {
            return doubleEndQueue.popFromHead();
        }
    }

}
